/*
 * @lc app=leetcode.cn id=33 lang=cpp
 *
 * [33] 搜索旋转排序数组
 */

// @lc code=start
class Solution {
public:
    int search(vector<int>& A, int x) {
        const int N = A.size();
        int l = 0, r = N;

        // 一个数组经过旋转之后，可以分为左边与右边
        // 左边是一个升序
        // 右边也是一个升序

        // 映射的总体思路:
        //
        // 1. 如果x在数组左边，比如
        // [4,5,6,7,0,1,2], x = 5
        // 那么把数组成处理成
        // [4,5,6,7,inf,inf,inf]再进行查找
        //
        // 2. 如果x在数组右边，比如：
        // [4,5,6,7,0,1,2], x = 1
        // 那么把左边部分的值全部设置成-inf
        // [-inf,-inf,-inf,-inf,0,1,2]
        // 再进行二分
        //

        // 判断一个元素在左边还是右边。
        // 一个元素如果大于等于A[0] => 那么就在左边
        // 在边半部分的值更大，所以用1表示。
        // 0表示右边的部分值更小。
        auto is_left = [&](const int v) {
            return v >= A[0];
        };

        auto x_pos = is_left(x);

        // 映射函数 => 返回A[m]与x的关系
        // {-1 = 小于； 0 = 相等； +1 = 大于x}
        //
        // 首先要判断x所在位置
        // 1. x在数组的左边
        //    a) 如果A[m]在数组的右边 -> 返回1
        //    b) 如果A[m]也在数组的左边 -> 根据A[m]与x的大小返回{-1,0,1}
        // 2. x在数组的右边
        //    c) 如果A[m]在数组的左边 -> 返回-1
        //    d) 如果A[m]也在数组的右边 -> 根据A[m]与x的大小返回{-1,0,1}
        //
        // 通过a), b), c), d)四种情况，我们可以发现
        // 在不同一边的时候，可以直接根据在左边还是在右边决定返回值。
        auto getC = [&](const int m) {
            auto m_pos = is_left(A[m]);
            // 都在同一边，那么直接比较大小
            if (x_pos == m_pos) {
                return A[m] == x ? 0 : (A[m] < x ? -1 : 1);
            }
            // 如果x在数组左边，那么m在数组右边
            // => 由于我们要把整个数组映射成一个有序的数组
            //    右边更小的部分我们要映射成 > x
            //    [4,5,6,7,0,1,2], x = 5 => [4,5,6,7,inf,inf,inf], x = 5
            //    映射成C[]数组就是[-1, 0, 1, 1, 1, 1, 1, 1]
            //    所以此时返回1
            // 如果x在数组右边，m在数组左边，左边的都设置成更小的。
            //    比如[4,5,6,7,0,1,2], x = 1
            // 那么把左边部分的值全部设置成-inf
            //    [-inf,-inf,-inf,-inf,0,1,2]
            //    映射成C[]数组就是[-1, -1, -1, -1, -1, 0, 1];
            //    所以m在左边 && x在右边，返回-1
            return x_pos ? 1 : -1;
        };

        while (l < r) {
            const int m = l + ((r-l)>>1);
            const int mov = getC(m);
            if (mov < 0) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return (l >= N || A[l] != x) ? -1 : l;
    }
};
// @lc code=end
